1. Field of the Invention
The present invention relates to an exponent calculation apparatus and method for performing exponent calculation including modular exponent calculation.
2. Description of the Related Art
Modular exponent calculation for calculating xe(mod N) is used in RSA cryptosystem/signature, ElGamal cryptosystem, DSA signature, Diffie-Hellman key agreement method, and so on. The modular exponent calculation is used not only in signature and decryption of files but also in security for communication paths, such as SSL. Calculation must be performed interactively in response to a communication request, and the processing efficiency has a great effect on cipher processing time.
Modular exponent calculation includes: a) modular square calculation x2(mod N); and b) modular multiplication calculation xu(mod N). Xe(mod N) is calculated by using a given e by a) and b). Some methods for increasing entire processing speed by reducing the number of multiplications a) and b) have been proposed.
An addition chain is a sequence of integers starting from a1=1 to an=e, where ai satisfies the sum of previous numbers (ai=aj+ak (j, k<i)). For example, when e=55, the addition chain is {1, 2, 3, 6, 12, 13, 26, 27, 54, 55}. This means that x55 can be calculated by performing calculations a) and b) in the order of x→x2→x3→x6→x12→x13→x26→x27→x54→x55. By using this method, the calculation amount can be reduced compared to a case where only b) is used: {1, 2, 3, 4, . . . , 52, 53, 54, 55}. In this way, an algorithm for finding a shorter addition chain for a given exponent e (55 in the above example) is effectively used.
<Binary Method>
Binary Method is an algorithm based on the above-described motivation, and is introduced in D. E. Knuth. The Art of Computer Programming: Seminumerical Algorithms, volume 2, Reading, Mass.: Addison-Wesley, Second edition (1981).
The Binary Method is an algorithm for performing the following processing. A given exponent e (bit length is k) is represented in binary notation: Σi=0, . . . , k−12i*e_i (e_i is 0 or 1). An algorithm in which x, e, and N are input and C=xe(mod N) is output is as follows:    1) if e_(k−1)=1 then C:=x else C:=1    2) for i=k−2 down to 0            2-1) C:=C*C(mod N)        2-2) if e_i=1 then C:=C*x(mod N)            3) return C
In the above algorithm, “for” in 2) represents that 2-1) and 2-2) are loop-processed while a variable i is reduced one after another from k−2 to 0. FIG. 2 shows a process of calculating x55(mod N) by using the Binary Method when e=55. In this case, the addition chain is {1, 2, 3, 6, 12, 13, 26, 27, 54, 55}.
<m-ary Method>
The m-ary Method is an expansion of the Binary Method, in which processing of 2 bits or more is performed at a time. An algorithm in which x, e, N are input and C=xe(mod N) is output is described below. However, the bit length of a given exponent e is k, and e is divided into r(=log2m) bit strings F_0, . . . , and F_(s−1), the number of the bit strings being s (s is an integer smaller than k/r).    0) xw(mod N) is pre-calculated for w=2, . . . , m−1    1) C:=x^{F_(s−1)} (mod N) (“^” represents exponentiation)    2) for i=s−2 down to 0            2-1) C:=Cm(mod N)        2-2) if F_i≠0 then C:=C*x^{F_i} (mod N)            3) return C
The m-ary Method is referred to as Quaternary Method when m=4. FIG. 3 shows a process according to the Quaternary Method when e=55. “e” in binary notation is (110111)2. By dividing this value by r=2 bits, (11 01 11)2 is obtained, which is processed in the manner shown in FIG. 3. In this case, the addition chain is {1, 2, 3, 6, 12, 13, 26, 52, 55}. In this method, the length of addition chain is shorter by one element than that in the Binary Method. Accordingly, the amount of modular calculation for calculating x55 can be reduced.
Furthermore, many improved methods, such as Slide Window Techniques, have been proposed as an expansion of the m-ary Method. In the Slide Window Techniques, the bit length used at a time in the process 2) of the algorithm can be changed, so as to reduce the amount of pre-calculation, which corresponds to the process 0) of the algorithm. Accordingly, the calculation amount and a region for storing pre-calculation result (referred to as table) can be reduced.
In the above-described prior arts, pre-calculation need not be performed and thus a table for storing pre-calculation result is not necessary in the Binary Method. However, in the Binary Method, when the number of 1 in an exponent e represented in binary notation is large, the amount of calculation is disadvantageously increased. On the other hand, in the Quaternary Method and the Slide Window Techniques, the calculation amount can be reduced. However, referring to a table is needed and the amount of pre-calculation is disadvantageously increased.